Recent advances in electronic and computer technologies have paved the way for the proliferation of wireless networks, e.g., distributed sensor networks which are mobile networks that include sensor nodes with limited computation and communication capabilities. Each sensor node is battery-powered and equipped with integrated sensors, data processing capabilities, and short range radio communications. Distributed sensor networks are dynamic in the sense that they allow addition and deletion of sensor nodes after deployment in a random manner over a terrain under scrutiny to expand the network or replace failing and unreliable sensor nodes. Distributed sensor networks may be deployed in hostile areas where communication is monitored and nodes are subject to capture and surreptitious use by an adversary. Hence, distributed sensor networks require cryptographic protection of communications, sensor capture detection, key revocation and sensor disabling.
Distributed sensor networks (DSNs) share several characteristics with the more traditional embedded wireless sensor networks (WSNs). Both include arrays of sensor nodes that are battery powered, have limited computational capabilities and memory, and rely on intermittent wireless communication via radio frequency and, possibly, optical links. Both include data-collection nodes, which cache sensor data and make it available for processing to application components of the network, as well as control nodes which monitor the status of and broadcast simple commands to sensor nodes. Although in both networks most nodes have limited, if any, mobility after deployment, some nodes are highly mobile (e.g., data collection and control nodes placed on humans, vehicles, aircraft).
However, distributed sensor networks (DSNs) differ from the traditional embedded wireless networks in several important areas, namely: their scale is orders of magnitude larger than that of embedded wireless networks (e.g., tens of thousands in DSNs as opposed to just tens of sensor nodes in WSNs); they are dynamic in the sense that they allow addition and deletion of sensor nodes after deployment to extend the network or replace failing and unreliable nodes without physical contact; and they may be deployed in hostile areas where communication is monitored and sensor nodes are subject to capture and manipulation by an adversary. These challenging operational requirements place equally challenging security constraints on DSN design.
Communication Security Constraints. The capabilities of the sensor nodes for large-scale DSNs range from those of Smart Dust sensors that have only 8 Kb of program and 512 bytes for data memory, and processors with 32 8-bit general registers that run at 4 MHz and 3.0V (e.g., the ATMEL 90LS8535 processor), to sensors that are over an order of magnitude more capable in terms of processing speed (e.g., the MIPS R4000 processors) and memory capacity. The power, energy and the related computational and communication limitations of nodes in this range make it impractical to use typical asymmetric (public-key) cryptosystems to secure communications. For example, in D. W. Carman, P. S. Kruus and B. J. Matt, “Constraints and Approaches for Distributed Sensor Network Security”, dated Sep. 1, 2000. NAI Labs Technical Report #00-010, available at http://download.nai.com/products/media/nai/zip/nailabs-report-00-010-final.zip, it is reported that on a mid-range processor, such as the Motorola MC68328 “DragonBall”, the energy consumption for a 1024-bit RSA encryption (signature) operation is much higher than that for a 1024-bit AES encryption operation; i.e., about 42 mJ (840 mJ) versus 0.104 mJ. Further, the energy consumption for transmitting a 1024-bit block over a distance of approximately 900 meters using a typical communication subsystems such as Sensoria WINS NG RF at 10 Kbps and 10 mW of power is about half that of RSA encryption (i.e., 21.5 mJ) and even less for reception (14.3 mJ). Substantially less energy is spent to communicate over smaller distances, since power is proportional to the square of the distance. Also, in the range of sensor capabilities, symmetric-key ciphers and hash functions are between two to four orders of magnitude faster than digital signatures. Hence, symmetric-key ciphers, low-energy, authenticated encryption modes, and hash functions are advantageous in protecting DSN communications.
Key Management Constraints. Traditional Internet style key exchange and key distribution protocols based on infrastructures using trusted third parties are impractical for large scale DSNs because of the unknown network topology prior to deployment, communication range limitations, intermittent sensor-node operation, and network dynamics. To date, the only practical options for the distribution of keys to sensor nodes of large-scale DSNs whose physical topology is unknown prior to deployment would be to rely on key pre-distribution. Keys would have to be installed in sensor nodes to accommodate secure connectivity between nodes. However, traditional key pre-distribution offers two inadequate solutions: either a single mission key or a set of separate keys, each being pair-wise privately shared with another node, must be installed in every sensor node.
The single mission-key solution is inadequate since the capture of any sensor node may compromise the entire DSN due to the fact that selective key revocation is impossible upon sensor-capture detection. In contrast, the pair-wise private sharing of keys between every two sensor nodes avoids wholesale DSN compromise upon node capture since selective key revocation becomes possible. However, this solution requires pre-distribution and storage of n−1 keys (n is the number of sensor nodes in the DSN) in each sensor node, and n(n−1)/2 per DSN, which renders it impractical for both intrinsic and technological reasons for DSNs using generally more than 10,000 nodes. Initially, pair-wise private key sharing between any two sensor nodes would be disadvantageous since direct node-to-node communication is achievable only in small node neighborhoods delimited by communication range and sensor density. Secondly, incremental addition and deletion as well as re-keying of sensor nodes would become both expensive and complex as they require multiple keying messages to be broadcast network-wide to all nodes during their non-sleep periods (i.e., one broadcast message for every added/deleted node or re-key operation). Third, a dedicated RAM memory for storing n−1 keys would push the on-chip, sensor-memory limits for the foreseeable future. Presently 64-bit, keys are used and would complicate fast key erasure upon detection of physical sensor tampering. Approximately 80 KB of dedicated key memory will have to be stored in RAM since keys can be dynamically added/deleted. This represents a substantial fraction of the on-chip RAM memories for the processors at the high end of the range considered.
It would be therefore highly desirable to have a simple key pre-distribution scheme that would require memory storage for only a few keys to a couple hundred keys and yet has similar security and superior operational properties when compared to those of the pair-wise private key sharing scheme.